1717F - Madoka and The First Session - CodeForces Solution

///Enta etfsh5t nseet el rank

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
        tree_order_statistics_node_update>;
#define pb push_back
#define F first
#define S second
#define f(i, a, b) for (int i = a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
//#define mp(x, y) make_pair(x, y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll

using ll = long long;
using ull = unsigned long long;
using uint = uint32_t;
using ii = pair<int, int>;

const int N = 1e5 + 6, LG = 18, MOD = 1e9 + 7;
const long double PI = acos(-1);

const long double EPS = 1e-9;


int a[N], s[N];
int u[N], v[N];
int deg[N];
int n, m;

struct FlowEdge {
    int v, u;
    long long cap, flow = 0;

    FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};

struct Dinic {
    const long long flow_inf = 1e18;
    vector<FlowEdge> edges;
    vector<vector<int>> adj;
    int n, m = 0;
    int s, t;
    vector<int> level, ptr;
    queue<int> q;

    Dinic(int n, int s, int t) : n(n), s(s), t(t) {
        adj.resize(n);
        level.resize(n);
        ptr.resize(n);
    }

    void add_edge(int v, int u, long long cap) {
        edges.emplace_back(v, u, cap);
        edges.emplace_back(u, v, 0);
        adj[v].push_back(m);
        adj[u].push_back(m + 1);
        m += 2;
    }

    bool bfs() {
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int id: adj[v]) {
                if (edges[id].cap - edges[id].flow < 1)
                    continue;
                if (level[edges[id].u] != -1)
                    continue;
                level[edges[id].u] = level[v] + 1;
                q.push(edges[id].u);
            }
        }
        return level[t] != -1;
    }

    long long dfs(int v, long long pushed) {
        if (pushed == 0)
            return 0;
        if (v == t)
            return pushed;
        for (int &cid = ptr[v]; cid < (int) adj[v].size(); cid++) {
            int id = adj[v][cid];
            int u = edges[id].u;
            if (level[v] + 1 != level[u] || edges[id].cap - edges[id].flow < 1)
                continue;
            long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
            if (tr == 0)
                continue;
            edges[id].flow += tr;
            edges[id ^ 1].flow -= tr;
            return tr;
        }
        return 0;
    }

    long long flow() {
        long long f = 0;
        while (true) {
            fill(level.begin(), level.end(), -1);
            level[s] = 0;
            q.push(s);
            if (!bfs())
                break;
            fill(ptr.begin(), ptr.end(), 0);
            while (long long pushed = dfs(s, flow_inf)) {
                f += pushed;
            }
        }
        return f;
    }
};

void doWork() {

    cin >> n >> m;
    Dinic flw(n + m + 5, 0, n + m + 1);
    f(i, 1, n + 1) cin >> s[i];
    f(i, 1, n + 1) cin >> a[i];
    f(i, 1, m + 1) {
        cin >> u[i] >> v[i];
        deg[u[i]] -= 1;
        deg[v[i]] -= 1;
        flw.add_edge(0, i, 1);
        flw.add_edge(i, m + u[i], 1);
        flw.add_edge(i, m + v[i], 1);
    }

    int totFlow = 0;
    f(i, 1, n + 1)if (s[i] == 1) {
            if ((a[i] - deg[i]) & 1) {
                cout << "NO\n";
                return;
            }
            if (a[i] < deg[i]) {
                cout << "NO\n";
                return;
            }
            flw.add_edge(m + i, n + m + 1, (a[i] - deg[i]) / 2);
            totFlow += (a[i] - deg[i]) / 2;
        }

    if (flw.flow() != totFlow) {
        cout << "NO\n";
        return;
    }
    f(i, 1, n + 1)if (!s[i])flw.add_edge(m + i, n + m + 1, 1e9);
    if (totFlow + flw.flow() != m) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    f(i, 1, m + 1) {
        int go;
        for (auto e: flw.adj[i])
            if (flw.edges[e].cap == flw.edges[e].flow && flw.edges[e].u != 0) {
                go = flw.edges[e].u - m;
                break;
            }
        if (u[i] == go)
            swap(u[i], v[i]);
        cout << u[i] << ' ' << v[i] << '\n';
    }


}

int32_t main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE

    int t = 1;
//    cin >> t;
    while (t--)
        doWork();
    return 0;
}